Transmission of data over a noisy channel is a fundamental problem in digital communication. A common solution to presence of noise or channel interference is to add redundancy to the transmitted information. The benefit of adding redundancy is that, although a receiver has access to only the noisy version of the transmitted signal, the receiver can use the redundancy to reconstruct the original information as it was transmitted from its source with high probability. This technique is referred to as Error Correcting Coding (ECC) or Error Control Coding.
A decoder may decode a received signal to determine the corresponding transmit signal for a given channel. A maximum likelihood (ML) decoder may determine the codeword in the transmitted signal that maximizes the probability associated with the ECC in the received signal. This maximum likelihood calculation is typically extremely complex and computationally intensive. For example, for a set of possible symbol values F, an ECC of length n symbols, and a code dimension k, the maximum likelihood (ML) decoder typically requires, e.g., O(n·|F|k) operations to decode the codeword, where O represents an order of magnitude. In some cases, the maximum likelihood decoder cannot keep up with the rate of incoming transmissions, causing delays in communication. Some decoders attempt to simplify these computations by using approximations of maximum likelihood (ML) computations, balancing error correction performance and decoding complexity. Such approximations, however, may cause degradation in the error correction accuracy and capability.
Due to the enormous rate at which information may be transmitted, there is a longstanding need inherent in the art for providing a fast and accurate solution to decode ECC signals.